package 二叉树练习题;

/**
 * 如何实现反向DNS查找缓存？分析与解答：要想实现反向DNS查找缓存，
 * 主要需要完成如下功能：
 * 1）将IP地址添加到缓存中的URL映射。
 * 2）根据给定IP地址查找对应的URL。
 * 对于本题的这种问题，常见的一种解决方案是使用哈希法（使用Hashmap来存储IP地址与URL之间的映射关系），
 * 由于这种方法相对比较简单，这里就不做详细的介绍了。
 * 下面重点介绍另外一种方法：Trie树。这种方法的主要优点如下：
 * 1）使用Trie树，在最坏的情况下的时间复杂度为O（1） ，
 * 而哈希方法在平均情况下的时间复杂度为O（1）；
 * 2）Trie树可以实现前缀搜索（对于有相同前缀的IP地址，可以寻找所有的URL）。
 * 当然，由于树这种数据结构本身的特性，
 * 所以使用树结构的一个最大的缺点就是需要耗费更多的内存，但是对于本题而言，这却不是一个问题，
 * 因为Internet IP地址只包含有11个字母（0～9和.）。所以，本题实现的主要思路：在Trie树中存储IP地址，
 * 而在最后一个结点中存储对应的域名。实现代码如下
 */
public class O如何实现反向DNS查找缓存 {

    /**
     * IP地址最多有11个不同的字符
     */
    private final int CHAR_COUNT = 11;

    private TrieNode root = new TrieNode();

    private class TrieNode {
        boolean isLeaf;
        String url;
        TrieNode[] child;//CHAR_COUNT;

        public TrieNode() {
            this.isLeaf = false;
            this.url = null;
            this.child = new TrieNode[CHAR_COUNT];
            for (int i = 0; i < CHAR_COUNT; i++) {
                child[i] = null;
            }
        }
    }

    public int getIndexFromChar(char c) {
        return (c == '.') ? 10 : (c - '0');
    }

    public char getCharFromIndex(int i) {
        return (i == 10) ? '.' : (char) ('0' + i);
    }

    //把一个ip地址和相应的url添加到trie树种，最后一个结点是url
    public void insert(String ip, String url) {
        int len = ip.length();
        TrieNode pCrawl = root;
        int level;
        for (level = 0; level < len; level++) {
            //根据当前遍历到的ip中字符，找出子节点的索引
            int index = getIndexFromChar(ip.charAt(level));

            //如果子节点不存在，则创建一个
            if (pCrawl.child[index] == null) {
                pCrawl.child[index] = new TrieNode();
            }
            //移动子节点
            pCrawl = pCrawl.child[index];
        }
        //在子节点中存储IP对应的URL
        pCrawl.isLeaf = true;
        pCrawl.url = url;
    }

    public String searchDNSCache(String ip) {
        TrieNode pCrawl = root;
        int len = ip.length();
        int level;

        //遍历IP地址中所有的字符
        for (level = 0; level < len; level++) {
            int index = getIndexFromChar(ip.charAt(level));
            if (pCrawl.child[index] == null) {
                return null;
            }
            pCrawl = pCrawl.child[index];
        }
        //返回找到的URL
        if (pCrawl != null && pCrawl.isLeaf) {
            return pCrawl.url;
        }
        return null;
    }

    public static void main(String[] args) {
        String[] ipAdds = {"10.57.11.127", "121.57.61.129", "66.125.100.103"};
        String[] url = {"www.sansung.com", "www.sansung.ney", "www.gogle.in"};
        int n = ipAdds.length;
        O如何实现反向DNS查找缓存 cache = new O如何实现反向DNS查找缓存();
        for (int i = 0; i < n; i++) {
            cache.insert(ipAdds[i], url[i]);
        }
        String ip = "121.57.61.129";
        String res_url = cache.searchDNSCache(ip);
        if (res_url != null) {
            System.out.println("找到了IP对应的URL;\n" + ip + "--->" + res_url);
        } else {
            System.out.println("没有找到对应的URL;\n");
        }
    }
}
